#ifndef HUFFMAN_BINARYTREE_H
#define HUFFMAN_BINARYTREE_H

#include "BinTreeNode.h"

template<typename Type>
void Huffman(Type *, int, BinaryTree<Type> &);

template<typename Type> 
class BinaryTree
{
public:

	BinaryTree(BinaryTree<Type> &bt1, BinaryTree<Type> &bt2)
	{
		m_proot = new BinTreeNode<Type>(bt1.m_proot->m_data 
			+ bt2.m_proot->m_data, bt1.m_proot, bt2.m_proot);
	}
	BinaryTree(Type item)
	{
		m_proot = new BinTreeNode<Type>(item);
	}
	BinaryTree(const BinaryTree<Type> &copy)
	{
		this->m_proot = copy.m_proot;
	}
	BinaryTree()
	{
		m_proot = NULL;
	}
	void Destroy()
	{
		m_proot->Destroy();
	}
	~BinaryTree()
	{
		//        m_proot->Destroy();
	}

	BinaryTree<Type>& operator=(BinaryTree<Type> copy);	//evaluate node
	friend void Huffman<Type>(Type *, int, BinaryTree<Type> &);
	friend bool operator < <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
	friend bool operator > <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
	friend bool operator <= <Type>(BinaryTree<Type> &l, BinaryTree<Type> & r);
	friend ostream& operator<< <Type>(ostream& ,BinaryTree<Type>&);	//output the data
private:
	BinTreeNode<Type> *m_proot;
	void Print(BinTreeNode<Type> *start,int n=0);	//print the tree with the root of start
};

template<typename Type> 
bool operator <(BinaryTree<Type> &l, BinaryTree<Type> &r)
{
	return l.m_proot->GetData() < r.m_proot->GetData();
}

template<typename Type> 
bool operator >(BinaryTree<Type> &l, BinaryTree<Type> &r)
{
	return l.m_proot->GetData() > r.m_proot->GetData();
}

template<typename Type> 
bool operator <=(BinaryTree<Type> &l, BinaryTree<Type> &r)
{
	return l.m_proot->GetData() <= r.m_proot->GetData();
}


template<typename Type> 
void BinaryTree<Type>::Print(BinTreeNode<Type> *start, int n)
{
	if(start==NULL){
		for(int i=0;i<n;i++)
		{
			cout<<"     ";
		}
		cout<<"NULL"<<endl;
		return;
	}
	Print(start->m_pright,n+1);	//print the right subtree
	for(int i=0;i<n;i++)
	{	//print blanks with the height of the node
		cout<<"     ";
	}
	if(n>=0)
	{
		cout<<start->m_data<<"--->"<<endl;//print the node
	}
	Print(start->m_pleft,n+1);	//print the left subtree
}

template<typename Type> 
ostream& operator<<(ostream& os,BinaryTree<Type>& out)
{
	out.Print(out.m_proot);
	return os;
}

template<typename Type> 
BinaryTree<Type>& BinaryTree<Type>::operator=(BinaryTree<Type> copy)
{
	m_proot=m_proot->Copy(copy.m_proot);
	return *this;
}

#endif